package BinaryTree;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;
import sun.font.CreatedFontTracker;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val){
            this.val = val;
        }
    }
    public List<TreeNode> list = new ArrayList<>();

    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A; //返回根节点
    }

    public void preOrder(TreeNode root){
        if (root == null){
            return;
        }
        System.out.print(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }


    public void inOder(TreeNode root){
        if (root  == null){
            return;
        }
        inOder(root.left);
        System.out.print(root.val);
        inOder(root.right);
    }

    public void postOder(TreeNode root){
        if (root == null){
            return;
        }
        inOder(root.left);
        inOder(root.right);
        System.out.print(root.val);
    }

    public List<TreeNode> preOrder2(TreeNode root){
        if (root == null){
            return null;
        }
        list.add(root);
        preOrder2(root.left);
        preOrder2(root.right);
        return null;
    }

    //获取树中节点个数
    //1.遍历方法
    int size = 0;
    public void nodeSize(TreeNode root){
        if (root == null){
            return;
        }
        size++;
        nodeSize(root.left);
        nodeSize(root.right);
    }

    //2.子方法
    //树中节点个数等于左树节点个数加右树节点个数加1
    public int nodeSize2(TreeNode root){
        if (root == null){
            return 0;
        }
        return nodeSize2(root.left)+nodeSize2(root.right)+1;
    }

    //获取叶子节点个数
    //1.遍历方法,
    public int leafSize = 0;
    public void getLeafSize(TreeNode root){
        if (root == null){
            return;
        }
        if (root.left == null && root.right == null){
            leafSize++;
        }
        getLeafSize(root.left);
        getLeafSize(root.right);
    }

    //2.子方法
    //叶子节点个数等于左树叶子节点个数加右树叶子节点个数
    public int getLeafSize2(TreeNode root){
        if (root == null)return 0;
        if (root.left ==null && root.right == null)return 1;
        return getLeafSize2(root.left)+getLeafSize2(root.right);
    }

    //获取第k层节点个数
    public int getKlevelNodeCount(TreeNode root,int k){
        if (root == null)return 0;
        if (k==1){
            return 1;
        }
        return getKlevelNodeCount(root.left, k-1) + getKlevelNodeCount(root.right, k-1);
    }

//获取二叉树高度
    public int getHigh(TreeNode root) {
     if (root == null) return 0;
     int leftHight = getHigh(root.left);
     int rightHight = getHigh(root.right);
    return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
    }

    //检测值为value的元素是否存在
    public boolean find(TreeNode root, char key){
        if (root == null){
            return false;
        }
        if (root.val == key){
            return true;
        }
        boolean leftval = find(root.left, key);
        if (leftval == true){
            return true;
        }
        boolean rightval = find(root.left, key);
        if (rightval == true){
            return true;
        }
        return false;
    }

    //层序遍历
    public void levelOrder(TreeNode root){
        Queue<TreeNode>q = new LinkedList<>();
        if (root == null){
            return;
        }
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            if (cur.left != null){
                q.offer(cur.left);
            }
            if (cur.right != null){
                q.offer(cur.right);
            }
            System.out.print(cur.val);
        }
    }

    //判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        Queue<TreeNode>q = new LinkedList<>();
        if (root == null){
            return true;
        }
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            if (cur != null){
                q.offer(cur.left);
                q.offer(cur.right);
            }else {
                break;
            }
        }
        while(!q.isEmpty()){
            if (q.poll() != null){
                return false;
            }
        }
        return true;
    }
}